A digital control or processing system, such as a computer system, may include one or more parts, such as memory devices, communication buses, and input/output devices, which are utilizable by other devices of the system as resources for the execution of system tasks. For example, processors may utilize memory as a source of data and instructions and as a resource for storage of results; the processors may also utilize input/output devices as resources for communicating with the outside world, and may utilize buses as communication paths between themselves and the memory or the input/output devices. Memory devices may likewise utilize buses as resources for sending information to processors, while input/output devices may utilize the buses as resources for sending information to memory devices and to processors.
Simultaneous use by a plurality of system devices of the same resource is likely to produce errors. For example, a processor reading data from a memory module while an input/output device is sending data to the memory module may obtain incorrect data; the output of an input/output device may be garbled when two processors simultaneously supply it with output information; and communications passing along a bus may become scrambled and nonsensical when they collide with each other.
It is therefore necessary to provide means within the system to control concurrent access by devices to the shared resources, and to allow only one device at a time to access and make use of a resource.
The prior art has generally concerned itself with controlling access to communication paths such as buses, and has provided preassigned fixed time slot allocation, and request arbitration techniques for this purpose.
Of these bus access control techniques, request arbitration has generally been the most efficient. Arbitration schemes require devices wishing to access a bus to request bus use from an arbitration mechanism, which mechanism then selects one from a set of simultaneous requests and grants bus use for a period or slot of time to the selected device. Bus arbitration schemes achieve bus use efficiency by granting time slots only to devices currently wishing to utilize the bus, unlike preassigned fixed time slot allocation schemes which grant time slots to devices irrespective of whether the devices have a need to utilize the bus at that time. Latency, or waiting time of units wishing to access the bus, is thus decreased in the arbitration schemes, and is further improved because using units wishing to use the bus can substantially immediately appraise the arbitration mechanism of this fact, without having to wait for a query from the arbitration mechanism. In contrast, a unit wishing to use the bus in a bus allocation system must wait until its predetermined allocated time slot arrives.
Conventional bus arbitration schemes generally implement a fixed, unchanging priority scheme among the using devices. Non programmable hardware logic generates bus use grant signals as a function of the incoming request signals and a fixed and unchanging priority structure. Such schemes are inflexible because the priority structure is built into the logic hardware and there is no way, short of redesigning the arbitration circuit, to accommodate different applications or changing system configurations and request loads.
The prior art has sought to alleviate these limitations by providing programmable arbitration mechanisms in which the relative priority ordering of the using devices is indicated by the contents of storage devices, such as registers, and hence may be changed by reprogramming the register contents.
While providing programmability at one level, these mechanisms have not met the needs of multiprocessor computer systems and other bus-oriented digital systems that require flexible, programmable, class-oriented priority schemes. In such systems, using devices are commonly divided into classes, with each class having a different priority, while devices within a class have the same priority and are generally scheduled to access the bus in a round-robin, equal opportunity, manner. The prior art programmable arbitration mechanisms have traditionally not possessed the flexibility necessary to adapt to such a variety and combination of priority determining manners. Hence the prior art mechanisms have not been capable of meeting the changing needs of a variety of arbitrator applications, configurations of using devices, and device response time requirements.